CF464D World of Darkraft - 2

首先明确一点,所有装备的期望相同,只需求出任意一种后答案乘 kk 即可。

dp[i][j]dp[i][j] 表示还需要打 ii 只怪,装备等级为 jj 的金币数量期望。

那么有三种情况:

1.得到的并不是当前类型装备,概率为 k1k\frac{k-1}{k},这种情况下你一分钱也得不到。

2.得到当前装备的 j+1j+1 级,概率为 1k×1j+1\frac{1}{k} \times \frac{1}{j+1},然后你可以得到 jj 元。

3.得到当前装备的 $[1,j] $ 级 ,概率为 1k×jj+1\frac{1}{k} \times\frac{j}{j+1}

此时金币的期望为 i=1ji×1j=j×(j+1)2j=j+12\sum_{i=1}^{j} i \times\frac{1}{j}=\frac{\frac{j \times (j+1)}{2}}{j}=\frac{j+1}{2}

用滚动数组优化一下,这样可以 n2n^2 转移。

但是 n105n \le 10^5 , 我们得优化一下。

我们要相信 Roma\mathrm{Roma} 跟我一样非,装备等级不会太高。

理性计算一下:

由上面分析可得,装备由 jj 级 到 j+1j+1 级的概率为 1k×(j+1)\frac{1}{k \times(j+1)} ,那么期望次数为 k×(j+1)k \times(j+1)

记期望最高等级为 ll,那么 2k+3k+...+lkn2k+3k+...+lk \le n

解得:

l<2(n+1)kl < \sqrt{\frac{2(n+1)}{k}}

理论上开 500500 即可,但这样有 0.00000020.0000002 的误差,开 525525 即可。

#include <cstdio>

const int MAXN = 525;
int n , k;
double dp[ 2 ][ MAXN + 5 ];

int main( ) {
    scanf("%d %d",&n,&k);
    
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= MAXN ; j ++ )
            dp[ i & 1 ][ j ] = ( dp[ ( i - 1 ) & 1 ][ j ] * ( ( k - 1 ) * 1.0 / k ) + ( dp[ ( i - 1 ) & 1 ][ j + 1 ] + j ) * ( 1.0 / ( k * ( j + 1 ) ) ) + ( dp[ ( i - 1 ) & 1 ][ j ] + ( 1 + j ) / 2.0 ) * ( j * 1.0 / ( k * ( j + 1 ) ) ) );
    
    printf("%.10f\n", dp[ n & 1 ][ 1 ] * k );
    return 0;
}